package algorithms.dynamicProgram;

import java.util.ArrayList;
import java.util.List;

public class LeetCode_300 {

    public static void main(String[] args) {
        int[] ints = {10,9,2,5,3,4};
        System.out.println(lengthOfLIS(ints));
    }


    /**
     * 二分法
     *
     * @param nums
     * @return
     */
    public static int lengthOfLIS(int[] nums) {
        List<Integer> lis = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            if (lis.size() > 0 && val <= lis.get(lis.size() - 1)) {
                int left = 0, right = lis.size()-1, mid = 0;
                // 查找第一个大于等于的数
                while (left <= right) {
                    mid = left + (right - left) / 2;
                    if (lis.get(mid) >= val) {
                        if (mid == 0 || lis.get(mid - 1) < val) {
                            break;
                        } else {
                            right = mid - 1;
                        }
                    } else {
                        left = mid + 1;
                    }
                }
                lis.set(mid,val);
            }else{
                lis.add(val);
            }
        }
        return lis.size();


    }


    public int lengthOfLIS1(int[] nums) {
        int[] dp = new int[nums.length];
        int max = 1;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }
}
